백준 13911 집 구하기

2017-12-26

백준 13911 집 구하기 문제는 맥도날드인 vertex에서 거리가 x이하이고 && 스세권의 vertex에서 거리가 y이하인 집을 찾는 문제이다. 단순히 맥도날드인 vertex, 스타벅스인 vertex에서 모두 다익스트라로 거리를 구해 만족하는 집들을 찾아내는 방법을 생각해도 맥도날드 또는 스타벅스의 수가 V-2개 까지 존재 할 수 있으므로 최악의 경우에 9998 * O(ElogV)를 해야하므로 시간초과가 발생한다.

하지만 이 문제에 대해 한번에 해결할 수 있는 방법이 있는데 맥도날드, 스세권으로 가는 cost가 0인 더미노드로 맥도날드 또는 스타벅스를 연결한뒤 다익스트라를 적용하는 것이다. 이 방법을 통해서 하게되면 맥도날드 1번, 스타벅스 1번의 다익스트라를 수행하는 것으로 문제를 풀 수 있다.

위의 그림처럼 각 정점으로의 거리의 배열 값을 구하게 되면 맥도날드, 혹은 스타벅스에서 각 정점으로의 최소거리를 구할 수 있고 조건에 따라 값을 출력해주기만 하면 된다.

#pragma warning(disable:4996)
#include<iostream>
#include<string.h>
#include<vector>
#include<cmath>
#include<queue>
#include<algorithm>
#define INF 987654321
using namespace std;

int v, e;
vector <vector<pair<int, int>>> adj;
int m, x;
int s, y;


void daikstra(priority_queue<pair<int, int>>& pq, vector<int>& dist)
{
	while (!pq.empty())
	{
		int totCost = -pq.top().first;
		int current = pq.top().second;
		int nextSize = adj[current].size();
		pq.pop();

		for (int i = 0; i < nextSize; i++)
		{
			int next = adj[current][i].first;
			int nextCost = adj[current][i].second;

			if (totCost + nextCost < dist[next])
			{
				dist[next] = totCost + nextCost;
				pq.push(make_pair(-dist[next], next));
			}
		}
	}
}

int main()
{
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &v, &e);
	adj.resize(v + 1);
	for (int i = 0; i < e; i++)
	{
		int s, e, c;
		scanf("%d %d %d", &s, &e, &c);
		adj[s].push_back(make_pair(e, c));
		adj[e].push_back(make_pair(s, c));
	}

	priority_queue<pair<int, int>> pq;
	vector<int> dist1(v + 1, INF);

	scanf("%d %d", &m, &x);
	for (int i = 0; i < m; i++)
	{
		int t;
		scanf("%d", &t);
		dist1[t] = 0;
		pq.push(make_pair(0, t));
	}

	daikstra(pq, dist1);

	scanf("%d %d", &s, &y);
	vector<int> dist2(v + 1, INF);

	for (int i = 0; i < s; i++)
	{
		int t;
		scanf("%d", &t);
		dist2[t] = 0;
		pq.push(make_pair(0, t));
	}
	daikstra(pq, dist2);

	
	int dis = INF;
	for (int i = 1; i < v + 1; i++)
		if (dist1[i] != 0 && dist2[i] != 0 && dist1[i]<=x && dist2[i]<=y && dist1[i] + dist2[i] < dis)
			dis = dist1[i] + dist2[i];

	dis != INF ? printf("%d\n", dis) : printf("-1\n");
		


}

Gunner

ProgrammingAlgorithm

백준 13911 집 구하기